package com.yanceysong.codetop.s51_s60;

import com.yanceysong.common.ListNode;


public class S51_Mid_2_两数相加 {
    /**
     * .LeetCode 第 2 题：两数相加 (Add Two Numbers)
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/add-two-numbers/">https://leetcode.cn/problems/add-two-numbers/</a>
     * .<p>
     * .【题目描述】
     * .给你两个 非空 的链表，表示两个非负的整数。
     * .它们每位数字都是按照 <b>逆序</b> 的方式存储的，并且每个节点只能存储一位数字。
     * .请你将两个数相加，并以相同形式返回一个表示和的链表。
     * .你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * .<p>
     * .【输入输出示例】
     * .示例1：
     * .输入：l1 = [2,4,3], l2 = [5,6,4]
     * .输出：[7,0,8]
     * .说明：342 + 465 = 807 （链表逆序存储：低位在前）
     * .<p>
     * .示例2：
     * .输入：l1 = [0], l2 = [0]
     * .输出：[0]
     * .<p>
     * .示例3：
     * .输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
     * .输出：[8,9,9,9,0,0,0,1]
     * .说明：9999999 + 9999 = 10009998 （重点：最高位进位额外增加一个节点）
     * .<p>
     * .【核心标签】链表 / 模拟 / 进位处理
     * .<p>
     * .【ASCII 图解】（示例1）
     * .  l1:  2 -> 4 -> 3  (代表数字342)
     * .  l2:  5 -> 6 -> 4  (代表数字465)
     * .逐位相加（含进位）：
     * .  2 + 5 = 7  (当前位=7, 进位=0)
     * .  4 + 6 = 10 (当前位=0, 进位=1)
     * .  3 + 4 + 1(进位) = 8 (当前位=8, 进位=0)
     * .结果：7 -> 0 -> 8  (代表数字807)
     * .<p>
     * .【解题思路】
     * .1. 使用两个指针分别遍历两个链表；当某一条链表已经结束则其当前值记为0。
     * .2. 每一位执行：sum = 值1 + 值2 + carry；新节点的值为 sum % 10；更新进位 carry = sum / 10。
     * .3. 循环结束后如果 carry > 0，需要在结果链表最后再补一个节点存储进位。
     * .4. 时间复杂度 O(max(m, n))，空间复杂度 O(1)（结果链表除外）。
     * .<p>
     * .【关键洞察】
     * .- 两数相加的“逐位 + 进位”逻辑本质与我们手算加法一致，只是链表已经按低位→高位逆序排列，使遍历顺序天然从最低位开始。
     * .- 只要确定：取值为空时补0 + 正确维护 carry + 循环结束后补最后可能的进位节点即可。
     * .- 由于每个节点只存一位数字（0-9），不会出现两位数，需要取余与除法的组合来分离“当前位”和“进位”。
     * .<p>
     * .【常见易错点】
     * .- 忘记链表长度不一致时需要把较短的链表视作补 0 继续相加。
     * .- 最终 carry > 0 时忘记再添加一个节点。
     * .- 使用头节点处理结果时初始化逻辑过于复杂。可以使用“哑节点”(dummy head) 简化实现。
     * .<p>
     * .【复杂度分析】
     * .- 时间：O(L)，L = max(len(l1), len(l2))
     * .- 空间：O(1)（不计结果链表额外开销）
     * .<p>
     * .【额外补充：为什么可以原地构造结果链表？】
     * .因为题目不要求复用原链表节点，也不要求修改输入；生成新链表更清晰与安全。
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 使用哑节点(dummy head) 简化“为空时初始化”逻辑
        ListNode dummyHead = new ListNode(-1);
        // 指向当前结果链表的末尾
        ListNode currentTail = dummyHead;
        // carry 保存当前进位（上一位的十位数字）
        int carry = 0;

        // 当任一链表未结束 或 存在未处理进位 时继续循环
        while (l1 != null || l2 != null || carry != 0) {
            // 安全取值：如果某条链表已经遍历完则视为 0
            int digit1 = (l1 != null) ? l1.val : 0;
            int digit2 = (l2 != null) ? l2.val : 0;

            // 当前位求和 + 上一轮的进位
            int sum = digit1 + digit2 + carry;

            // 当前节点值为个位；新的进位为十位
            int newDigit = sum % 10;
            carry = sum / 10;

            // 追加新节点到结果链表尾部
            currentTail.next = new ListNode(newDigit);
            currentTail = currentTail.next;

            // 前进两个输入链表指针
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        // dummyHead.next 才是结果链表真正的头结点
        return dummyHead.next;
    }

    // ======================== 测试与工具方法 ========================

    /**
     * .构造一个链表（按给定顺序逆序存储数字的每一位）。
     * .例如 buildList(2,4,3) 表示数字 342。
     */
    private static ListNode buildList(int... digits) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for (int d : digits) {
            cur.next = new ListNode(d);
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * .将链表转换为字符串形式，便于打印/debug。
     */
    private static String listToString(ListNode head) {
        if (head == null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        ListNode cur = head;
        while (cur != null) {
            sb.append(cur.val);
            if (cur.next != null) sb.append(',');
            cur = cur.next;
        }
        sb.append(']');
        return sb.toString();
    }

    /**
     * .比较两个链表的值序列是否完全一致。
     */
    private static boolean equalsList(ListNode a, ListNode b) {
        while (a != null && b != null) {
            if (a.val != b.val) return false;
            a = a.next;
            b = b.next;
        }
        return a == null && b == null;
    }

    /**
     * .单个测试用例执行与结果校验。
     */
    private static void runTest(int caseId, ListNode l1, ListNode l2, ListNode expected) {
        S51_Mid_2_两数相加 solver = new S51_Mid_2_两数相加();
        ListNode actual = solver.addTwoNumbers(l1, l2);
        String expStr = listToString(expected);
        String actStr = listToString(actual);
        boolean pass = equalsList(actual, expected);
        System.out.printf("Case %02d => Input1=%s, Input2=%s | Output=%s | Expected=%s | %s\n",
                caseId, listToString(l1), listToString(l2), actStr, expStr, pass ? "PASS" : "FAIL");
        assert pass : "测试用例 " + caseId + " 未通过";
    }

    public static void main(String[] args) {
        System.out.println("=== 两数相加测试开始 ===");

        // 用例1：题目示例 342 + 465 = 807
        runTest(1,
                buildList(2, 4, 3),
                buildList(5, 6, 4),
                buildList(7, 0, 8));

        // 用例2：两个链表都是单节点 0 + 0 = 0
        runTest(2,
                buildList(0),
                buildList(0),
                buildList(0));

        // 用例3：长度不一致，且最终需要新增最高位进位 9999 + 1 = 10000
        runTest(3,
                buildList(9, 9, 9, 9),
                buildList(1),
                buildList(0, 0, 0, 0, 1));

        // 用例4：一条链表为 0，另一条为多位数 0 + 81 = 81
        runTest(4,
                buildList(0),
                buildList(1, 8), // 表示 81
                buildList(1, 8));

        // 用例5：全 9 触发连续进位 9999999 + 9999 = 10009998
        runTest(5,
                buildList(9, 9, 9, 9, 9, 9, 9),
                buildList(9, 9, 9, 9),
                buildList(8, 9, 9, 9, 0, 0, 0, 1));

        // 用例6：两个较长随机数 123456789 + 987654321 = 1111111110
        // 逆序表示：987654321 -> [9,2,3,4,5,6,7,8,9] (注意：这里直接写就是逆序位)
        // 构造：123456789 -> [9,8,7,6,5,4,3,2,1]
        // 和：1111111110 -> 0,1,1,1,1,1,1,1,1,1
        runTest(6,
                buildList(9, 8, 7, 6, 5, 4, 3, 2, 1),
                buildList(9, 8, 7, 6, 5, 4, 3, 2, 1), // 实际这里为了简化使用同样数字 => 987654321 + 987654321 = 1975308642
                // 计算 987654321 + 987654321 = 1975308642 => 逆序链表: [2,4,6,8,0,3,5,7,9,1]
                buildList(2, 4, 6, 8, 0, 3, 5, 7, 9, 1));

        // 用例7：一个为空（按题意非空，但这里做鲁棒性测试） + 非空
        runTest(7,
                null,
                buildList(1, 2, 3),
                buildList(1, 2, 3));

        // 用例8：两个均只有一个节点且会产生进位 5 + 7 = 12 -> [2,1]
        runTest(8,
                buildList(5),
                buildList(7),
                buildList(2, 1));

        // 用例9：多次连续进位 9->9->9 与 9->9->9 -> 999 + 999 = 1998 => [8,9,9,1]
        runTest(9,
                buildList(9, 9, 9),
                buildList(9, 9, 9),
                buildList(8, 9, 9, 1));

        // 用例10：其中一条链表比另一条长：123 + 7890 = 8013
        // 123 -> [3,2,1] ; 7890 -> [0,9,8,7]
        // 结果 8013 -> [3,1,0,8]
        runTest(10,
                buildList(3, 2, 1),
                buildList(0, 9, 8, 7),
                buildList(3, 1, 0, 8));

        System.out.println("=== 所有测试完成 ===");
        System.out.println("(提示：若需启用 assert 校验，请运行时添加 -ea 参数)");
    }
}
